﻿// 4333. 高速公路.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://www.acwing.com/problem/content/4336/

某国家有 N
 个城市，编号 1∼N
。

其中第 i
 个城市的位置坐标为 (xi,yi)
。

该国家的高速公路系统十分差劲，到目前为止只有 M
 对城市之间存在高速公路直接连接。

因此，政府决定新修一些高速公路，从而使得任意两个城市之间都能通过高速公路互相抵达。

已知高速公路都是双向的，且任意两个城市之间要修建或已修建的高速公路的长度都等于两城市之间的直线距离。

为了节约成本，政府希望新修的高速公路的长度之和尽可能小。

请你提供一种合适的修建方案。

注意，每个高速公路必须在一端城市进入，然后在另一端城市离开，不存在中途离开或变道的可能。

输入格式
第一行包含整数 N
。

接下来 N
 行，每行包含两个整数 xi,yi
。

再一行包含整数 M
。

最后 M
 行，每行包含两个整数 a,b
，表示城市 a
 和 b
 之间存在一条高速公路。每对城市之间最多存在一条高速公路。

输出格式
若干行，每行包含两个整数，表示一条新修道路的两端城市编号。

如果无需新修任何高速公路，则输出空文件即可。

如果方案不唯一，输出任意合理方案均可。

数据范围
1≤N≤750
,
0≤M≤1000
,
−10000≤xi,yi≤10000
,
1≤a,b≤N
。

输入样例：
9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2
输出样例：
1 6
3 7
4 9
5 7
8 3
*/
int main()
{
    std::cout << "Hello World!\n";
}

 